1. Field of the Invention
This invention relates to memory management, and more specifically to apparatus and methods for efficiently implementing remembered sets in region-based garbage collectors.
2. Background of the Invention
In an object-oriented managed runtime, such as the Java Virtual Machine (JVM), Microsoft Common Language Runtime (CLR), or Smalltalk runtime, the primary memory resource is a garbage-collected object heap. The object heap provides memory for objects, each of which is an instance of a class. All managed runtimes support object garbage collection. Garbage collection attempts to reclaim memory occupied by garbage, which may include objects, data, or other areas in memory that are no longer in use by programs.
Various different approaches exist for collecting garbage on the object heap. One approach is to divide the object into a number of equally-sized regions. One example of a collector that uses such an approach is Sun's Garbage-First collector. In order to reduce pause times, a region-based collector may perform garbage collection on a subset of the total number of regions in the object heap. This subset may be referred to as a “collection set.” To properly perform garbage collection on a collection set, the collector needs to discover references from objects outside of the collection set to objects inside of the collection set. These references are remembered in what is known as a “remembered set.”
Various different approaches have been utilised or proposed for implementing a remembered set. Some of these approaches, however, are not applicable to general region-based garbage collectors, because they make assumptions about regions in the collection set. For example, one prior art approach only remembers references from “older” generations to “younger” generations. Such assumptions may not be applicable to generalized region-based garbage collectors, which may operate on arbitrary sets of regions in the collection set.
Other approaches have high space overhead, meaning that they consume a large amount of memory as a percentage of the object heap. For example, using the popular SPECjbb® benchmark, one test showed that the Garbage-First collector's remembered set consumed space equivalent to thirty percent of the object heap. Even after applying various optimizations to the Garbage-First remembered set, the remembered set still consumed as much as twenty percent of the object heap.
In view of the foregoing, what is needed is a more efficient approach for implementing a remembered set for region-based garbage collectors. Ideally, such an approach will work for any arbitrary set of regions in the collection set. Such an approach will also ideally minimize the amount of memory used as a percentage of the object heap.